Ngày 4 tháng 11 năm 1991, trong phiên họp đầu tiên của Kỳ họp Đại hội đồng INTERPOL lần thứ 60 tại thành phố Punta del Este, Uruguay, Đại hội đồng INTERPOL đã chính thức thông qua đơn xin gia nhập Tổ chức của Bộ Nội vụ (nay là Bộ Công an) Việt Nam với đa số phiếu tán thành. Lực lượng Cảnh sát Việt Nam đã chính thức trở thành thành viên thứ 156 của Tổ chức INTERPOL, mở ra một cơ chế hợp tác đa phương về thực thi pháp luật trên phạm vi rộng nhất từ trước đến nay. (Ngày 4/11 là ngày truyền thống của Lực lượng INTERPOL Việt Nam).[1]

Trước yêu cầu thực tiễn của công tác đấu tranh phòng chống tội phạm xuyên quốc gia, tội phạm có yếu tố nước ngoài tại Việt Nam, ngày 28/5/1993, Bộ trưởng Bộ Nội vụ đã ký Quyết định thành lập Văn phòng INTERPOL Việt Nam trực thuộc Tổng cục Cảnh sát (nay là Tổng cục Cảnh sát phòng chống tội phạm).[1]

Ngày 17 tháng 9 năm 2014, Văn phòng Interpol Việt Nam thuộc Tổng cục Cảnh sát được hợp nhất với Vụ Hợp tác quốc tế thuộc Bộ Công an trở thành Cục Đối ngoại trực thuộc Bộ Công an.[9]